package algorithms.leaning.class21;

import common.util.MyUtil;

/**
 * 给定5个参数，N，M，row，col，k
 * 表示在N*M的区域上，醉汉Bob初始在(row,col)位置
 * Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
 * 任何时候Bob只要离开N*M的区域，就直接死亡
 * 返回k步之后，Bob还在N*M的区域的概率
 *
 * @author guichang
 * @date 2021/6/23
 */

@SuppressWarnings("all")
public class Code5_动态规划_醉汉生存概率 {

    public static void main(String[] args) {
        int N = 10, M = 10, row = 0, col = 0, k = 2;
        MyUtil.print(survive(N, M, row, col, k));
        MyUtil.print(surviveDp(N, M, row, col, k));
    }

    public static double survive(int N, int M, int row, int col, int k) {
        if (N <= 0 || M <= 0 || row < 0 || col < 0 || k < 0) {
            return -1;
        }
        // 所有可能性4^k次方
        return process(N - 1, M - 1, row, col, k) / Math.pow(4, k);
    }

    /**
     * 当前位置在[i,j]还剩rest步有几种走法
     *
     * @param N 最大横坐标，范围-1
     * @param M 最大纵坐标，范围-1
     */
    private static int process(int N, int M, int i, int j, int rest) {
        if (i < 0 || i > N || j < 0 || j > M) {
            return 0;
        }
        // 走完了还在里面就算一种
        if (rest == 0) {
            return 1;
        }
        // 可以向上下左右走
        int p1 = process(N, M, i - 1, j, rest - 1);
        int p2 = process(N, M, i + 1, j, rest - 1);
        int p3 = process(N, M, i, j - 1, rest - 1);
        int p4 = process(N, M, i, j + 1, rest - 1);
        return p1 + p2 + p3 + p4;
    }

    public static double surviveDp(int N, int M, int row, int col, int k) {
        if (N <= 0 || M <= 0 || row < 0 || col < 0 || k < 0) {
            return -1;
        }
        int[][][] dp = new int[N][M][k + 1];
        // 第0层全是1
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dp[i][j][0] = 1;
            }
        }
        for (int rest = 1; rest <= k; rest++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    // 可以向上下左右走
                    dp[i][j][rest] += getDp(dp, i - 1, j, rest - 1);
                    dp[i][j][rest] += getDp(dp, i + 1, j, rest - 1);
                    dp[i][j][rest] += getDp(dp, i, j - 1, rest - 1);
                    dp[i][j][rest] += getDp(dp, i, j + 1, rest - 1);
                }
            }
        }
        // 所有可能性4^k次方
        return dp[row][col][k] / Math.pow(4, k);
    }

    private static int getDp(int[][][] dp, int i, int j, int rest) {
        if (i < 0 || i >= dp.length || j < 0 || j >= dp[0].length) {
            return 0;
        }
        return dp[i][j][rest];
    }


}